package leetcode_500;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *@author 周杨
 *ConcatenatedWords_472 跟wordBreak一样 AC 54%
 *see:https://segmentfault.com/a/1190000008233766
 *2018年8月29日 下午4:03:11
 */
public class ConcatenatedWords_472 {
	public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> result = new ArrayList<String>();
        Set<String> set = new HashSet<String>(Arrays.asList(words));
        for(String word : words) {
            set.remove(word);
            if(wordBreak(set, word)) result.add(word);
            set.add(word);
        }
        return result;
    }
    
    private boolean wordBreak(Set<String> words, String s) {
        if(s == null || s.length() == 0) return false;
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i < dp.length; i++) {
            for(int j = i-1; j >= 0; j--) {
                if(dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
